package com.zjj.algorithm.learning.atguigu.algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * 骑士周游问题算法
 *
 * @author zjj_admin
 * @date 2023/1/7 14:39
 */
public class HorseChessboard {

    /**
     * X 表示横坐标（第几列）
     */
    private static final int X = 7;

    /**
     * Y 表示纵坐标（第几行）
     */
    private static final int Y = 6;

    /**
     *
     */
    private static final int[][] visited = new int[Y][X];

    private static boolean finished;

    private static int  count = 1;


    public static void main(String[] args) {
        ChessPoint point = new ChessPoint(3, 1);
        int[][] board = new int[Y][X];
        long start = System.currentTimeMillis();

        traversalChessboard(board, point, 1);
        System.out.println("count = " + count);
        long end = System.currentTimeMillis();
        System.out.println("用时：" + (end - start) + " ms");
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }

    }

    /**
     * @param board 棋盘
     * @param curr  位置
     * @param step  第几步
     */
    public static void traversalChessboard(int[][] board, ChessPoint curr, int step) {
        board[curr.y][curr.x] = step;
        visited[curr.y][curr.x] = 1;
        List<ChessPoint> next = next(curr);
        //遍历下一个点
        while (!next.isEmpty()) {
            ChessPoint point = next.remove(0);
            if (board[point.y][point.x] == 0) {
                count ++;
                traversalChessboard(board, point, step + 1);
                visited[point.y][point.x] = 1;
            }
        }
        if (step < X * Y && !finished) {
            board[curr.y][curr.x] = 0;
            visited[curr.y][curr.x] = 0;
        } else {
            finished = true;
        }
    }

    /**
     * 获取当前点的下一个可以走的点
     *
     * @param currPoint
     * @return
     */
    public static List<ChessPoint> next(ChessPoint currPoint) {
        List<ChessPoint> res = new ArrayList<>();
        int currX, currY;
        currX = currPoint.x - 2;
        if (currX >= 0) {
            compareX(currPoint, res, currX);
        }
        currX = currPoint.x + 2;
        if (currX <= X - 1) {
            compareX(currPoint, res, currX);
        }
        currY = currPoint.y - 2;
        if (currY >= 0) {
            compareY(currPoint, res, currY);
        }

        currY = currPoint.y + 2;
        if (currY <= Y - 1) {
            compareY(currPoint, res, currY);
        }
        return res;
    }

    /**
     * 当确定 X 后比较 Y
     *
     * @param currPoint
     * @param res
     * @param currX
     */
    private static void compareX(ChessPoint currPoint, List<ChessPoint> res, int currX) {
        int currY;
        currY = currPoint.y - 1;
        if (currY >= 0) {
            res.add(new ChessPoint(currX, currY));
        }
        currY = currPoint.y + 1;
        if (currY <= Y - 1) {
            res.add(new ChessPoint(currX, currY));
        }
    }

    /**
     * 当确定 Y 后比较 X
     *
     * @param currPoint
     * @param res
     * @param currY
     */
    private static void compareY(ChessPoint currPoint, List<ChessPoint> res, int currY) {
        int currX;
        currX = currPoint.x - 1;
        if (currX >= 0) {
            res.add(new ChessPoint(currX, currY));
        }
        currX = currPoint.x + 1;
        if (currX <= X - 1) {
            res.add(new ChessPoint(currX, currY));
        }
    }
}


/**
 * 棋盘坐标
 */
class ChessPoint {

    /**
     * 横坐标
     */
    int x;
    /**
     * 纵坐标
     */
    int y;

    public ChessPoint(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "{" +
                "x=" + x +
                ", y=" + y +
                '}';
    }
}